//
// Created by 高森森 on 2022/1/25.
//

#ifndef LEETCODE_SOLUTION6_H
#define LEETCODE_SOLUTION6_H
#include<iostream>
using namespace std;
#include<vector>
#include<unordered_map>
#include<queue>
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
class Solution6 {
public:
    unordered_map <Node*,Node*>visited;
    Node* cloneGraph(Node* node) {
        if(node== nullptr)
            return node;
        if(visited.find(node)!=visited.end())
        {
            return visited[node];
        }
        Node* copynode=new Node(node->val);
        visited[node]=copynode;
        for(auto neigh:node->neighbors)
        {
            copynode->neighbors.push_back(cloneGraph(neigh));
        }
        return copynode;
    }
    Node* cloneGraph2(Node* node) {
        if(node== nullptr)
            return node;
        //将第一个节点加入队列并且复制
        queue<Node*>queue;
        queue.push(node);
        Node *copynode=new Node(node->val);
        visited[node]=copynode;
        while(!queue.empty())
        {
            Node* node=queue.front();
            queue.pop();
            //复制队列的邻居节点，如果未访问过就加入队列，构造节点的邻居关系
            for(auto neigh:node->neighbors)
            {
                if(visited.find(neigh)==visited.end())
                {
                    Node * n=new Node(neigh->val);
                    visited[neigh]=n;
                    queue.push(neigh);
                }
                visited[node]->neighbors.push_back(visited[neigh]);
            }
        }
        return visited[node];
    }
};


#endif //LEETCODE_SOLUTION6_H
